Implement euclidean algorithm to compute GCD¶
Implement euclidean algorithm to compute the greatest common divisor (GCD).
Expected output:
304 = 2 * 150 + 4
150 = 37 * 4 + 2
4 = 2 * 2 + 0
gcd is 2
………
6 = 2 * 3 + 0
gcd is 3
from math import *
def euclid_algo(x, y, verbose=True):
if x < y: # We want x >= y
return euclid_algo(y, x, verbose)
print()
while y != 0:
if verbose:
print('%s = %s * %s + %s' % (x, floor(x/y), y, x % y))
x, y = y, x % y
if verbose:
print('gcd is %s' % x)
return x
# test
euclid_algo(150, 304)
# 304 = 2 * 150 + 4
# 150 = 37 * 4 + 2
# 4 = 2 * 2 + 0
# gcd is 2
euclid_algo(1000, 10)
# 1000 = 100 * 10 + 0
# gcd is 10
euclid_algo(150, 9)
# 150 = 16 * 9 + 6
# 9 = 1 * 6 + 3
# 6 = 2 * 3 + 0
# gcd is 3